package main

//链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gong-shui-san-xie-sheng-cheng-suo-you-yo-7l45/
func main() {

}

func generateParenthesisByDFS(n int) []string {
	result = make([]string, 0)
	dfs(0, 2*n, 0, n, "")
	return result
}

/**
 * i: 当前遍历到位置
 * n: 字符总长度
 * score: 当前得分，令 '(' 为 1， ')' 为 -1
 * max: 最大得分值
 * path: 当前的拼接结果
 */
func dfs(i, n, score, max int, path string) {
	if i == n {
		if score == 0 {
			result = append(result, path)
		}
	} else {
		// 如果添加左括号后不超过 max（有效值），则可以添加
		if score+1 <= max {
			dfs(i+1, n, score+1, max, path+"(")
		}

		// 如果添加右括号后不少于 0（有效值），则可以添加
		if score-1 >= 0 {
			dfs(i+1, n, score-1, max, path+")")
		}
	}
}
